package com.hard;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

/**
 * Created by Lxk on 2020/2/15.
 */
public class Solution630 {

    public static class Course implements Comparable<Course> {

        int courseTime;

        int courseFinTime;

        Course(int courseTime, int courseFinTime) {
            this.courseTime = courseTime;
            this.courseFinTime = courseFinTime;
        }

        @Override
        public int compareTo(Course o) {
            return this.courseFinTime == o.courseFinTime ?
                    this.courseTime - o.courseTime : this.courseFinTime - o.courseFinTime;
        }
    }

    public int scheduleCourse(int[][] courses) {
        List<Course> courseList = new ArrayList<>();
        for (int[] course : courses) {
            courseList.add(new Course(course[0], course[1]));
        }
        Collections.sort(courseList);
        int curTime = 0;
        PriorityQueue<Course> courseQueue = new PriorityQueue<>((a, b) -> b.courseTime - a.courseTime);
        for (int i = 0; i < courseList.size(); i++) {
            Course course = courseList.get(i);
            if (curTime + course.courseTime <= course.courseFinTime) {
                curTime += course.courseTime;
                courseQueue.offer(course);
            } else if (!courseQueue.isEmpty() && courseQueue.peek().courseTime > course.courseTime) {
                curTime += (course.courseTime - courseQueue.poll().courseTime);
                courseQueue.offer(course);
            }
        }
        return courseQueue.size();
    }

    public static void main(String[] args) {
        int[][] courses = {{5, 5}, {4, 6}, {2, 6}};
        Solution630 solution630 = new Solution630();
        System.out.println(solution630.scheduleCourse(courses));
    }

}
